#include <string>
#include <iostream>
#include <vector>
#include <fstream>
#include "util.h"

#ifndef _SUFFIXINDEX_H_
#define _SUFFIXINDEX_H_


int64 comparison_counter;
int64 hash_counter; 
int64 identical_character_counter;
int64 bisection_comparison_counter;
int64 direct_comparison_counter;

// Counter is an int32 or an int64, used to ennumerate the positions
// Value must support < and =
template <class Counter, class Value> struct SuffixIndex {
  void RandomData(Counter length) {
    data_size_ = length;
    data_ = new Value[data_size_];
    for (Counter i=0; i < length; i++) {
      data_[i] = rand();
    }
  }
  void LoadData(string filename) {
    uchar * block;
    int64 length;
    Mmap(filename, &block, &length);
    int64 data_size = length / sizeof(Value);
    data_size_ = data_size;
    CHECK(data_size_ = data_size); // Make sure the data size fits in a Counter
    data_ = (Value *)(block);
  }
  void BuildIndex() {
    IndexRollingHash();
    index_ = new Counter[data_size_];
    for (Counter i=0; i<data_size_; i++) index_[i] = i;
    sort(index_, index_ + data_size_, PositionCompare(this));
    /*for (int i=0; i+1<data_size_; i++) {
      Counter comp = CompareSuffixes(index_[i], index_[i+1]);      
      CHECK(CompareSuffixes(index_[i], index_[i+1]) < 0);
      CHECK(CompareSuffixes(index_[i+1], index_[i]) > 0);
      }*/
  }
  void StoreIndex(string filename) {
    ofstream out(filename.c_str(), ios::out | ios::binary);
    out.write((const char *)index_, data_size_ * sizeof(Counter));
  }
  void LoadIndex(string filename) {
    uchar * block;
    int64 length;
    Mmap(filename, &block, &length);
    CHECK(length == (data_size_) * sizeof(Counter));
    index_ = (Counter *)(block);
  }

  /*
    This index allows a rolling hash over any subsequence to be computed in O(1)
    We store some elements of a virtual array a defined by 
    a[-1] = 0
    a[i] = k * a[i-1] + s[i] (mod n)
    
    the hash of a substring 
    = s[begin .. end) = a[end-1] - a[begin-1] * k^(end-begin)
  */
  void IndexRollingHash() {
    k_ = 9084723423141ll;
    k_pow_2_pow_n_ = new uint64[100];
    k_pow_2_pow_n_[0] = k_;
    for (int i=1; i<100; i++) 
      k_pow_2_pow_n_[i] = k_pow_2_pow_n_[i-1] * k_pow_2_pow_n_[i-1];
    rolling_hash_sparsity_ = 4;
    rolling_hash_ = new uint64[data_size_ / rolling_hash_sparsity_];
    uint64 last_val = 0;
    for (Counter i=0; i<data_size_; i++) {
      last_val = last_val * k_ + data_[i];
      if (i % rolling_hash_sparsity_ == 0) 
	rolling_hash_[i / rolling_hash_sparsity_] = last_val;
    }
  }
  /* 
     returns a[n-1], as defined above. 
     The hash of a substring s[begin .. end) 
     = PointRollingHash(end) - k^end-begin * PointRollingHash(begin)
  */
  int64 PointRollingHash(Counter n) {
    if (n==0) return 0;
    n--;
    uint64 ret = rolling_hash_[n / rolling_hash_sparsity_];
    for (Counter i = (n / rolling_hash_sparsity_) * rolling_hash_sparsity_ + 1; 
	 i<=n; i++) {
      ret = ret * k_ + data_[i];
    }
    return ret;
  }

  // Only for debugging
  int64 ComputeRollingHash(int begin, int end){
    hash_counter++;
    return PointRollingHash(end) - PointRollingHash(begin) 
      * UInt64Pow(k_, end - begin);
  }

  struct Searcher{
  Searcher(SuffixIndex *si, Value *target_begin, 
	   Counter target_length, bool second_wins) 
  :si_(si), target_begin_(target_begin), 
      target_length_(target_length), second_wins_(second_wins) {}
    bool operator() (int64 position) {
      Counter p = si_->index_[position];
      return 
	Compare(si_->data_ + p, si_->data_size_ - p,
		target_begin_, target_length_, second_wins_) >= 0;
    }
    Value * target_begin_;
    Counter target_length_;
    SuffixIndex *si_;
    bool second_wins_;
  };

  // Input string is represented by a pointer and length
  // Output is a range in the index.
  void Search(Value *target_begin, Counter target_length,   // what you search for
	      Counter ** match_begin, Counter ** match_end  // return values
	      ) {
    Searcher s(this, target_begin, target_length, false);
    *match_begin = index_ + FirstSatisfaction(0, data_size_, s);
    s.second_wins_ = true;
    *match_end = index_ + FirstSatisfaction(0, data_size_, s);
  }

  // Getting called during search, not during indexing. 
  // lexicographically compare two strings represented by pointer and length
  // comparisons return positive/negative/zero, a la strcmp
  // If second_wins is true, 
  //     compare s1 to s2+$, where $ represents an infinitely large value
  static Counter Compare(Value *v1, Counter l1, 
			 Value *v2, Counter l2, bool second_wins = false) {
    if (v1 == v2) return 0;
    Counter shorter = min(l1, l2);
    for (Counter c=0; c<shorter; c++) {
      if (v1[c] < v2[c]) return -1;
      if (v2[c] < v1[c]) return 1;      
    }
    if (second_wins && (shorter == l2)) return -1;
    return l1 - l2;
  }

  // lexicographic compare of suffixes starting from positions p1 and p2
  // strcmp style return value
  Counter CompareSuffixes(Counter p1, Counter p2) {
   if (p1 == p2) return 0;
    comparison_counter++;
    Counter l1 = data_size_ - p1;
    Counter l2 = data_size_ - p2;
    Counter shorter = min(l1, l2);
    int log_step = 7;
    Counter step = (1 << log_step);
    // Do some amount of naive comparison to see if we have an early difference.
    for (Counter i=0; i<step; i++) {
      if (i == shorter) return (l1 < l2) ? -1 : 1;
      if (data_[p1+i] < data_[p2+i]) return -1;
      if (data_[p2+i] < data_[p1+i]) return 1;
      identical_character_counter++;
      direct_comparison_counter++;
    }    
    identical_character_counter -= step;
    bisection_comparison_counter++;
    // Here we find the largest value n such that the first n values starting at
    // p1 are equal to the first n values starting at p2.  
    uint64 point_hash_1 = PointRollingHash(p1);
    uint64 point_hash_2 = PointRollingHash(p2);
    uint64 point_hash_difference = point_hash_1 - point_hash_2;
    // we know that low <= n < high 
    Counter low = step;
    uint64 k_pow_low = k_pow_2_pow_n_[log_step];
    Counter high = shorter + 1;
    while (low + 1 != high) {
      // our step should be at least 1, but less than high-low
      log_step++;
      step *= 2;
      while (low + step >= high) {
	log_step--;
	step /= 2;
      }
      Counter mid = low + step;
      uint64 k_pow_mid = k_pow_low * k_pow_2_pow_n_[log_step];
      bool match = ( (PointRollingHash(p1 + mid) - PointRollingHash(p2 + mid)
		      - point_hash_difference * k_pow_mid) == 0);
      if (match) {
	low = mid;
	k_pow_low = k_pow_mid;
      } else {
	high = mid;
      }
    }
    identical_character_counter += low;
    if (low == shorter) return (l1 < l2) ? -1 : 1;
    // for (Counter i=0; i<low; i++) CHECK(data_[p1+i] == data_[p2+i]);
    // CHECK(data_[p1+low] != data_[p2+low]);
    return (data_[p1+low] < data_[p2+low]) ? -1 : 1;
  }

  struct PositionCompare {
    PositionCompare(SuffixIndex * si) {      
      si_ = si;
    }
    SuffixIndex *si_;
    bool operator()(Counter c1, Counter c2) {
      return (si_->CompareSuffixes(c1, c2) < 0);
    }
  };

  Value *data_; // the raw data - a fl
  Counter data_size_;
  Counter * index_;

  // stuff related to rolling hash
  uint64 * rolling_hash_;
  int rolling_hash_sparsity_;
  uint64 k_;
  uint64 * k_pow_2_pow_n_; // maps n -> k_ ^ (2 ^ n)

};

void suffixindex_main();

#endif
